#include "FFT_simple.h"

complex* FFT_simple(complex *input, int N){
	
	complex *sincos, *output;
	complex w;
	int i, j, k;
	float f, g;
	int w_index, w_inc, i_inc, v_index;
	int fs1 = N - 1;
	int fs2 = N / 2;
 	float old1_re, old1_im, old2_re, old2_im;
	
	
	sincos = (complex*) malloc(sizeof(complex) * N);
	output = (complex*) malloc(sizeof(complex) * N);
	
	
	g = 2.0 * (PI / (float) N);
	for(i=0; i < N ; i++){
	    f = g * (float)i;
	    sincos[i].re = cos(f);
	    sincos[i].im = -sin(f);/*FFT*/
	    //sincos++;
	  }
	
	  
	  for(k=0; k < N; k++)
	    {
	      output[k].re = input[k].re;
	      output[k].im = input[k].im;
	    }
	    
	    i_inc = fs2;
	    w_inc = 1;
	    for(i=1; i < N; i<<=1)
	    {
	      v_index = 0;
	      for(j=0; j<i; j++)
	      {
	        w_index = 0;
	        for(k=0; k<i_inc; k++)
	        {
	          old1_re = output[v_index].re;
	          old1_im = output[v_index].im;
	          old2_re = output[v_index+i_inc].re;
	          old2_im = output[v_index+i_inc].im;
	          
	          w.re = sincos[w_index].re;
	          w.im = sincos[w_index].im;
	          output[v_index+i_inc].re = (old1_re - old2_re)*w.re - (old1_im - old2_im)*w.im;
	          output[v_index+i_inc].im = (old1_im - old2_im)*w.re + (old1_re - old2_re)*w.im;
	          output[v_index].re = old1_re + old2_re;
	          output[v_index].im =  old1_im + old2_im;
	          w_index += w_inc;
	          v_index++;
	        }
	        v_index += i_inc;
	      }
	      w_inc <<= 1;
	      i_inc >>= 1;
	    }
	    
	    j = 0;
	    for(i=1;i<fs1;i++)
	    {
	      k = fs2;
	      while(k <= j)
	      {
	        j = j - k;
	        k >>= 1;
	      }
	      j = j + k;
	      if(i < j)
	      {
	        old1_re = output[j].re;
	        old1_im = output[j].im;
	        output[j].re = output[i].re;
	        output[j].im = output[i].im;
	        output[i].re = old1_re;
	        output[i].im = old1_im;
	    
	      }
	    }
	    
	   return output;
	  
	}
